//
//  ListNode.swift
//  Swift刷算法
//
//  Created by 卢悦明 on 2020/12/25.
//
import Foundation

/// 单向链表
class ListNode<T: Equatable> {

    public var val: T
    public var next: ListNode?
    init(_ val: T) {
        self.val = val
        self.next = nil
    }
    init(_ val: T, next: ListNode?) {
        self.val = val
        self.next = next
    }
    init(_ node: ListNode) {
        self.val = node.val
        self.next = node.next
    }
}
extension ListNode : CustomStringConvertible {
    public var description: String {
        return "\(self.val)"
    }
}


/// 打印和构造方法
struct LinkedList<T: Equatable> {

    var size: Int = 0
    private var firstNode: ListNode<T>?
    
    // 添加节点
    mutating func add(_ index: Int, value: T) {
        guard index >= 0 else {
            return
        }
        if index == 0 {
            firstNode = ListNode(value, next: firstNode)
        } else {
            let perNode = nodeOfIndex(index - 1)
            let newNode = ListNode(value, next: perNode?.next)
            perNode?.next = newNode
        }
        size += 1
    }
    // 删除节点
    mutating func remove(_ index: Int) -> T? {
        guard index >= 0 && index < size else {
            return nil
        }
        var node = firstNode
        if index == 0 {
            firstNode = firstNode?.next
        } else {
            let per = nodeOfIndex(index-1)
            node = per?.next
            per?.next = node?.next
        }
        size -= 1
        return node?.val
    }
    // 修改节点
    func setNode(_ index: Int, value: T) -> T? {
        let node = nodeOfIndex(index)
        let temp = node?.val
        node?.val = value
        return temp
    }
    // 查询节点
    func getNode(_ index: Int) -> T? {
        let node = nodeOfIndex(index)
        return node?.val
    }
    // 获取某个节点的位置
    func indexOf(_ value: T) -> Int {
        var tempNode = firstNode
        for i in 0..<size {
            if tempNode?.val == value {
                return i
            }
            tempNode = tempNode?.next
        }
        return -1
    }
//    清空数据
    mutating func clear() {
        size = 0
        firstNode = nil
    }
    // 通过索引获取节点
    func nodeOfIndex(_ index: Int) -> ListNode<T>? {
        guard index >= 0 && index < size else {
            print("=============", index)
            return nil
        }
        var temp: ListNode<T>? = firstNode;
        for _ in 0..<index {
            temp = temp?.next
        }
        return temp
    }
    
    
}

extension LinkedList {
    
    // 通过数组创建一个单项链表
    mutating func creatList(array: [T]) -> ListNode<T>? {
        guard array.count != 0 else {
            return nil
        }
        let nodeArray = array.compactMap { ListNode($0) }
        let head = ListNode(array[0])
        var temp = head
        for node in nodeArray {
            temp.next = node
            temp = node
        }
        temp.next = nil
        size = array.count
        firstNode = head.next
        return head.next
    }
    
    // 打印一个单项链表
    static func printList(_ headNode: ListNode<T>?) {
        var head = headNode
        var index = 0
        var printArray = [String]()
        while let tempHead = head {
            printArray.append("\(tempHead.val)->")
            head = head!.next
            index += 1
        }
        printArray.append("nil")
        var printStr = ""
        printArray.forEach { printStr = printStr + $0 }
        print(printStr)
    }
    
    func printList() {
        LinkedList.printList(firstNode)
    }
}

